Nearly all forms of electronic communication and storage systems use error-correcting codes. Error correcting codes compensate for the intrinsic unreliability of information transfer in these systems by introducing redundancy into the data stream. The mathematical foundations of error correcting were established by Shannon. Shannon developed the mathematical concept of the channel in which distortion of signals in communications systems is modeled as a random process. The most fundamental result of Shannon is the Noisy channel theorem, which defines for the channel a capacity, a quantity that specifies the maximum rate at which information can be reliably delivered through the channel. This capacity is known as Shannon capacity. Reliable transmission at rates approaching capacity requires the use of error correcting codes. Thus, error-correcting codes are designed to achieve sufficient reliability while approaching capacity as closely as possible. Recent advances in error correcting coding systems resulting from the invention of turbo codes and the subsequent rediscovery and development of low-density parity-check (LDPC) codes offer coding systems of feasible complexity that can approach Shannon's capacity quite closely.
Extrinsic information in the context of information being extracted from a soft input-soft output unit is feedback information obtained by processing a previous input to the soft-input and soft-output unit. The previous input information is referred to as prior information. If there is no prior information, e.g., in the case of a first processing iteration, then the extrinsic information being extracted from the soft-input soft output unit is information obtained by a null value being substituted for the prior information of the soft-input and soft output unit.
Extrinsic information in the context of information being supplied to a soft input-soft output unit is feedback information obtained by processing a previous output of the soft-input and soft-output unit. In this case the extrinsic information being fed back to the soft-input and soft-output unit is usually interpreted as prior information to the soft-input and soft-output unit. If there is no previous output, e.g., in the case of a first processing iteration, the extrinsic information being supplied to the soft-input soft output unit is information obtained by a null value being substituted for a previous output of the soft-input and soft output unit.
LDPC codes and turbo codes are examples of iterative coding systems. Such systems are normally implemented using interconnected soft input-soft output signal processing modules. Generally, such modules implement a maximum a posteriori (MAP) algorithm, or approximate such an algorithm. In such a module there are generally one or two inputs and the purpose is to estimate a vector of quantities X=x1, . . . , xn which we shall assume to be binary, e.g., in {0,1}. The two inputs are a vector of soft values Z, which represent some external observation from, e.g., a communications channel, and another vector of soft values W=w1, . . . , wn which represent prior information on the bits x1, . . . , xn. Typically the prior information takes the form of bitwise independent log-likelihood ratios
      w    i    =      log    ⁢                  ⁢          (                        p          ⁡                      (                                          x                i                            =                              0                ❘                U                                      )                                    p          ⁡                      (                                          x                i                            =                              1                ❘                U                                      )                              )      where U is some information assumed independent of Z. The MAP algorithm associated to the signal processing module computes the posterior log-likelihood ratio, given by
      log    ⁢                  ⁢          (                        p          ⁡                      (                                                            x                  i                                =                                  0                  ❘                  W                                            ,              Z                        )                                    p          ⁡                      (                                                            x                  i                                =                                  1                  ❘                  W                                            ,              Z                        )                              )        ,for each bit xi depending possibly on sum assumed relationship between X, U and Z. Related to the posterior log-likelihood ratio is the so-called extrinsic information associated to the calculation. In many implementations of such systems, extrinsic information is given by
            log      ⁢                          ⁢              (                              p            ⁡                          (                                                                    x                    i                                    =                                      0                    ❘                    W                                                  ,                Z                            )                                            p            ⁡                          (                                                                    x                    i                                    =                                      1                    ❘                    W                                                  ,                Z                            )                                      )              -          w      i        ,which is ideally equal to
      log    ⁢                  ⁢          (                        p          ⁡                      (                                                            x                  i                                =                                  0                  ❘                                      W                    ⁢                    \                    ⁢                                          w                      i                                                                                  ,              Z                        )                                    p          ⁡                      (                                                            x                  i                                =                                  1                  ❘                                      W                    ⁢                    \                    ⁢                                          w                      i                                                                                  ,              Z                        )                              )        ,for each xi. The extrinsic information represents the information about bit xi provided by the computation excluding the information explicitly provided in the prior information about the bit xi. In practice one approximates
  log  ⁢          ⁢      (                  p        ⁡                  (                                                    x                i                            =                              0                ❘                                  W                  ⁢                  \                  ⁢                                      w                    i                                                                        ,            Z                    )                            p        ⁡                  (                                                    x                i                            =                              1                ❘                                  W                  ⁢                  \                  ⁢                                      w                    i                                                                        ,            Z                    )                      )  this through quantization and/or by other means and it is generally understood that practical forms of extrinsic information may not precisely satisfy the mathematical definition. Extrinsic information need not be limited to the particular example given here which is provided as a common example of one type of extrinsic information which is frequently used in the context of some message passing decoders.
LDPC codes are well represented by bipartite graphs, often called Tanner graphs; see FIG. 1 diagram 100, in which one set of nodes, the variable nodes 102, corresponds to bits of the codeword and the other set of nodes, the constraint nodes 104, sometimes called check nodes, correspond to the set of parity-check constraints which define the code. Edges 106 in the graph connect variable nodes 102 to constraint nodes 106. The number of edges connected to a node is known as the degree of the node. A variable node and a constraint node are said to be neighbors if they are connected by an edge in the graph. One typically assumes that a pair of nodes is connected by at most one edge. In this case, an LDPC code can equivalently be represented using a parity check matrix. FIG. 2 presents an exemplary illustration 200 where the indicated vector X 202 is a codeword if and only if H X=0, where H 204 is a parity check matrix. Illustration 200 may be an alternate representation of diagram 100 for an exemplary LDPC code.
To each variable node is associated one bit of the codeword. In some cases some of these bits might be punctured. Punctured bits may be desirable in certain code structures and they are excluded from the transmitted codeword.
A bit sequence associated one-to-one with the variable node sequence is a codeword of the code if and only if, for each constraint node, the bits neighboring the constraint (via their association with variable nodes) sum to zero modulo two, i.e., they comprise an even number of ones.
Each variable node in the graph is initially provided with a soft bit, termed a received value, that indicates an estimate of the associated bit's value as determined by observations from, e.g., the communications channel. Ideally, the estimates for separate bits are statistically independent. This ideal can be, and often is, violated in practice. A collection of received values constitutes a received word. For purposes of this application we may identify the received word with the prior information provided to the decoder. The decoders and decoding algorithms used to decode LDPC codewords operate by exchanging messages along the edges of the Tanner graph. The nodes compute the messages usually as a function of the incoming messages, including the received value in the case of variable nodes. Such algorithms will be generally referred to as message-passing algorithms.
It will be appreciated that received words generated in conjunction with IDPC coding, can be processed by performing LDPC decoding operations thereon, e.g., error correction and detection operations, to generate a reconstructed version of the original codeword. The reconstructed codeword is made up of the hard decisions associated to the bit-wise posterior information computed by the decoder. The reconstructed codeword can then be subject to data decoding to recover the original data that was coded. The data decoding process may be, e.g., simply selecting a specific subset of the bits from the reconstructed codeword.
As mentioned above, LDPC decoding operations generally comprise message-passing algorithms. There are many potentially useful message-passing algorithms and the use of such algorithms is not limited to LDPC decoding. One of the most powerful of such algorithms is known as belief propagation. Belief propagation uses MAP decoding at each of the nodes in the Tanner graph together with exchange of messages along the edges of the graph. To facilitate an understanding of the invention discussed in the sections that follow, we will now give a brief mathematical description of belief propagation.
Belief propagation for (binary) LDPC codes can be expressed as follows. Messages transmitted along the edges of the graph are interpreted as log-likelihood ratios
  log  ⁢          ⁢            p      0              p      1      for the bit associated to the variable node. Here, (p0,p1) represents a conditional probability distribution on the associated bit where px denotes the probability that the bit takes the value x. The prior information provided to the decoder is normally also given in the form of a log-likelihood. In general, a message m represents the log-likelihood ratio m and a received value or prior information y represents the log-likelihood ratio y. For punctured bits the log-likelihood ratio received value y is set to 0, indicating p0=p1=½.
Let us describe the message-passing rules of belief propagation. Messages are denoted by mC2V for messages from check nodes to variable nodes and by mV2C for messages from variable nodes to check nodes. Consider a variable node with d edges. For each edge j=1, . . . , d let mC2V(i) denote the incoming message on edge i. At the initialization of the decoding process we set mC2V=0 for every edge. In general, outgoing messages from variable nodes are given by
            m      V2C        ⁡          (      j      )        =      y    +          (                        ∑                      i            =            1                    d                ⁢                              m            C2V                    ⁡                      (            i            )                              )        -                            m          C2V                ⁡                  (          j          )                    .      
The outgoing decoded soft value from a node (not an edge message) corresponding to this operation is given by
      x    out    =      y    +                  (                              ∑                          i              =              1                        d                    ⁢                                    m              C2V                        ⁡                          (              i              )                                      )            .      This value is posterior information provided by the decoder. The outgoing hard decision associated to this output is obtained from the sign of xout. The extrinsic information associated to the given bit is similarly given by
      (                  ∑                  i          =          1                d            ⁢                        m          C2V                ⁡                  (          i          )                      )    .The output posterior and extrinsic information depend on the number of iterations performed. This is because the information expressed in these outgoing quantities increases, at least in principle, with the number of iterations performed.
At the check nodes, also sometimes referred to as constraint nodes, the update can be expressed in several ways. One mathematically convenient form for a check node of degree d is the following
                    m        C2V            ⁡              (        j        )              =                  tanh                  -          1                    ⁡              (                              ∏                          i              =              1                        d                    ⁢                                    tanh              ⁡                              (                                                      m                    V2C                                    ⁡                                      (                    i                    )                                                  )                                      /                          tanh              ⁡                              (                                                      m                    V2C                                    ⁡                                      (                    j                    )                                                  )                                                    )              ,
Turbo equalizers shall now be described. Many communications or storage channels of interest exhibit intersymbol interference (ISI). When ISI is present each symbol observed at the receiver has contributions from several transmitted symbols. This can be interpreted as an observation of the nominal or desired symbol in the presence of interference from other symbols. Typically, part of the signal processing that occurs at the receiver in such a case is dedicated to removing or reducing ISI. For the illustrative purposes we shall assume that the transmitted symbols are binary, e.g., bits. ISI removal occurs in soft-input soft-output signal processing module that will be referred to as an ISI detector. The ISI detector is assume to have inputs Z, corresponding to raw information provided by the channel, and prior information W on the bits X that constitute the transmitted symbols. Often, the bits X are additionally constrained in that they also form a codeword of, e.g., an LDPC code or a turbo code. With LDPC or turbo decoding, extrinsic information about transmitted symbols produced as part of the decoding process can be used as prior information by the ISI detector.
If the extrinsic information generated during decoding is fed back to the ISI detector, then ISI removal can normally be improved. This then enables the ISI detector to provide improved estimates (soft values in the form of the extrinsic information from the detector) to the decoder, which then is able to feed back better information to the detector. Such a process is used to perform turbo equalization.
FIG. 3 is a drawing 300 depicting a turbo equalization process. Turbo equalizers are schemes in which equalization or ISI removal is performed in conjunction with soft decoding, such as LDPC or turbo code decoding in a feedback scheme where extrinsic information produced by the decoder is used by the equalizer as prior information to improve its performance and the extrinsic information produced by the ISI detector is used as prior information (received values) by the decoder. Through the feedback of extrinsic information both MAP signal processing modules, the ISI detector and decoder improve the performance of the other thereby improving the overall performance of the system information provided to the decoder.
FIG. 3 includes an ISI detector 302 and an iterative decoder 304, e.g., and LDPC or turbo decoder. External input 306, e.g., received signal observed at the receiver including ISI are input to the ISI detector 302. The ISI detector 302, using its knowledge of interfering symbols and the nature of the interference, generates extrinsic information 308, e.g. soft values, and feeds the extrinsic information 308 about the transmitted symbols, e.g., bits, to the prior input of the iterative decoder 304. (In the first pass, when there is no prior information about the transmitted symbols available to the detector from the decoder, the extrinsic information is set equal to the posterior information.) The iterative decoder 304, performs soft decoding, e.g., using a message passing algorithm. As part of the decoding process, extrinsic information 310 about the transmitted symbols, e.g., soft values, is generated and fed back to the ISI detector 302 as prior information. The ISI detector 302, can use the extrinsic information 310 as prior information on the transmitted symbols to improve the removal of ISI and generate new soft values 308. The new extrinsic information 308 now supplied to the iterative decoder 304 is an improved prior. This can result in an improved decoding by the iterative decoder 304 and improved extrinsic information 310 being fed back to the ISI detection. This iterative process can continue. At some point, the rate of performance increase decreases, and it may be decided that performing further iterations would not be productive. The iterative decoder 304 outputs the decisions of the decoder, e.g., the decoded information 312 with an associated probability.
The algorithms used in Turbo Equalization are typically message-passing schemes. There is a great deal of literature on turbo equalization. One of the references is the following: C. Douillard, M. Jezequel, C. Berrou, A. Picart, P. Didier, A. Glavieux, “Iterative correction of intersymbol interference:turbo equalization,” European Transactions Telecommunication, vol. 6, pp. 507-511, September-October 1995. Turbo Equalization may be used with LPDC codes.
While Turbo Equalization in the context of message passing decoders has proven very beneficial in many cases, in some cases during decoding improvements in the input to an iterative message passing decoder cease to result in improvements in the decoding result. It would be desirable if methods and/or apparatus could be developed to improve the ability of an iterative decoder to take advantage of improvements in the input to the decoder in at least some cases where the improvement in the decoder input might not have a beneficial impact on the ultimate decoding result.